home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / ICONX_FO / RSTRUCT.C < prev    next >
Text File  |  1990-03-02  |  15KB  |  467 lines
  1. /*
  2.  * File: rstruct.c
  3.  *  Contents: addmem, cplist, cpset, hmake, hchain, hgener, hgrow, hshrink, memb
  4.  */
  5.  
  6. #include "::h:config.h"
  7. #include "::h:rt.h"
  8. #include "rproto.h"
  9.  
  10. /*
  11.  * addmem - add a new set element block in the correct spot in
  12.  *  the bucket chain.
  13.  */
  14.  
  15. novalue addmem(ps,pe,pl)
  16. union block **pl;
  17. struct b_set *ps;
  18. struct b_selem *pe;
  19.    {
  20.    ps->size++;
  21.    if (*pl != NULL )
  22.       pe->clink = *pl;
  23.    *pl = (union block *) pe;
  24.    }
  25.  
  26. /*
  27.  * cplist(dp1,dp2,i,j) - copy sublist dp1[i:j] into dp2.
  28.  */
  29.  
  30. int cplist(dp1, dp2, i, j)
  31. dptr dp1, dp2;
  32. word i, j;
  33.    {
  34.    register dptr dp;
  35.    word size, nslots;
  36.    struct b_list *lp1, *lp2;
  37.    struct b_lelem *bp1, *bp2;
  38.  
  39.    /*
  40.     * Calculate the size of the sublist and fail if it's less than 0.
  41.     *  Also round nslots up to the minimum list block size.
  42.     */
  43.    size = nslots = j - i;
  44.  
  45.    /*
  46.     * Get pointers to the list and list elements for the source list
  47.     *  (bp1, lp1) and the sublist (bp2, lp2).
  48.     */
  49.    if (blkreq(sizeof(struct b_list) + sizeof(struct b_lelem) +
  50.          nslots * sizeof(struct descrip)) == Error)
  51.       return Error;
  52.    lp1 = (struct b_list *) BlkLoc(*dp1);
  53.    bp1 = (struct b_lelem *) lp1->listhead;
  54.    lp2 = (struct b_list *) alclist(size);
  55.    bp2 = (struct b_lelem *) alclstb(nslots, (word)0, size);
  56.    lp2->listhead = lp2->listtail = (union block *) bp2;
  57.    dp = bp2->lslots;
  58.  
  59.    /*
  60.     * Locate the block containing element i in the source list.
  61.     */
  62.    if (size > 0) {
  63.       while (i > bp1->nused) {
  64.          i -= bp1->nused;
  65.          bp1 = (struct b_lelem *) bp1->listnext;
  66.          }
  67.       }
  68.  
  69.    /*
  70.     * Copy elements from the source list into the sublist, moving to
  71.     *  the next list block in the source list when all elements in a
  72.     *  block have been copied.
  73.     */
  74.    while (size > 0) {
  75.       j = bp1->first + i - 1;
  76.       if (j >= bp1->nslots)
  77.          j -= bp1->nslots;
  78.       *dp++ = bp1->lslots[j];
  79.       if (++i > bp1->nused) {
  80.          i = 1;
  81.          bp1 = (struct b_lelem *) bp1->listnext;
  82.          }
  83.       size--;
  84.       }
  85.  
  86.    /*
  87.     * Fix type and location fields for the new list.
  88.     */
  89.    dp2->dword = D_List;
  90.    BlkLoc(*dp2) = (union block *) lp2;
  91.    return Success;
  92.    }
  93.  
  94. /*
  95.  * cpset(dp1,dp2,n) - copy set dp1 to dp2, reserving memory for n entries.
  96.  */
  97. int cpset(dp1, dp2, n)
  98. dptr dp1, dp2;
  99. word n;
  100.    {
  101.    register union block **tp, *ep, *old, *new;
  102.    register struct b_slots *seg;
  103.    register word i, slotnum;
  104.  
  105.    /*
  106.     * Make a new set organized like dp1, with room for n elements.
  107.     */
  108.    new = hmake(T_Set, BlkLoc(*dp1)->set.mask + 1, n);
  109.    if (new == NULL)
  110.       return Error;
  111.    /*
  112.     * Copy the header and slot blocks.
  113.     */
  114.    old = BlkLoc(*dp1);
  115.    new->set.size = old->set.size;    /* actual set size */
  116.    new->set.mask = old->set.mask;    /* hash mask */
  117.    for (i = 0; i < HSegs && old->set.hdir[i] != NULL; i++)
  118.       memcopy((char *)new->set.hdir[i], (char *)old->set.hdir[i],
  119.          old->set.hdir[i]->blksize);
  120.    /*
  121.     * Work down the chain of element blocks in each bucket
  122.     *    and create identical chains in new set.
  123.     */
  124.    for (i = 0; i < HSegs && (seg = new->set.hdir[i]) != NULL; i++)
  125.       for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--)  {
  126.          tp = &seg->hslots[slotnum];
  127.          for (ep = *tp; ep != NULL; ep = *tp) {
  128.             *tp = (union block *)alcselem(&ep->selem.setmem, ep->selem.hashnum);
  129.             (*tp)->selem.clink = ep->selem.clink;
  130.             tp = &(*tp)->selem.clink;
  131.             }
  132.          }
  133.    dp2->dword = D_Set;
  134.    BlkLoc(*dp2) = new;
  135.    if (TooSparse(new))
  136.       hshrink(dp2);
  137.    return Success;
  138.    }
  139.  
  140. /*
  141.  * hmake - make a hash structure (Set or Table) with a given number of slots.
  142.  *  hmake also ensures adequate storage for *nelem* elements, but does not
  143.  *  allocate then.  If *nslots* is zero, a value appropriate for *nelem*
  144.  *  elements is chosen.
  145.  */
  146. union block *hmake(tcode, nslots, nelem)
  147. int tcode;
  148. word nslots, nelem;
  149.    {
  150.    word seg, t, nbytes, blksize, elemsize;
  151.    union block *blk;
  152.  
  153.    if (nslots == 0)
  154.       nslots = (nelem + MaxHLoad - 1) / MaxHLoad;
  155.    for (seg = t = 0; seg < (HSegs - 1) && (t += segsize[seg]) < nslots; seg++)
  156.       ;
  157.    nslots = ((word)HSlots) << seg;    /* ensure legal power of 2 */
  158.    if (tcode == T_Table) {
  159.       blksize = sizeof(struct b_table);
  160.       elemsize = sizeof(struct b_telem);
  161.       }
  162.    else {    /* T_Set */
  163.       blksize = sizeof(struct b_set);
  164.       elemsize = sizeof(struct b_selem);
  165.       }
  166.    nbytes = blksize + (seg + 1) * (sizeof(struct b_slots) - (HSlots*WordSize)) +
  167.       nslots * WordSize + nelem * elemsize;
  168.    if (blkreq(nbytes) == Error)
  169.       return NULL;                /* sorry, no memory */
  170.    blk = alchash(tcode);
  171.    for (; seg >= 0; seg--)
  172.       blk->set.hdir[seg] = alcsegment(segsize[seg]);
  173.    blk->set.mask = nslots - 1;
  174.    return blk;
  175.    }
  176.  
  177. /*
  178.  * hchain - return a pointer to the word that points to the head of the hash
  179.  *  chain for hash number hn in hashed structure s.
  180.  */
  181.  
  182. /*
  183.  * lookup table for log to base 2; must have powers of 2 through (HSegs-1)/2.
  184.  */
  185. static unsigned char log2[] = {
  186.    0,1,2,2, 3,3,3,3, 4,4,4,4, 4,4,4,4, 5,5,5,5, 5,5,5,5, 5,5,5,5, 5,5,5,5,
  187.    };
  188.  
  189. union block **hchain(pb, hn)
  190. union block *pb;
  191. register uword hn;
  192.    {
  193.    register struct b_set *ps;
  194.    register word slotnum, segnum, segslot;
  195.  
  196.    ps = (struct b_set *)pb;
  197.    slotnum = hn & ps->mask;
  198.    if (slotnum >= HSlots * sizeof(log2))
  199.       segnum = log2[slotnum >> (LogHSlots + HSegs/2)] + HSegs/2;
  200.    else
  201.       segnum = log2[slotnum >> LogHSlots];
  202.    segslot = hn & (segsize[segnum] - 1);
  203.    return &ps->hdir[segnum]->hslots[segslot];
  204.    }
  205.  
  206. /*
  207.  * hgener - agent function to generate the elements of a hashed structure.
  208.  *
  209.  *  Arg1 = set or table to enumerate
  210.  *  Arg2 = integer value indicating desired action:
  211.  *     0   generate set elements
  212.  *     1   generate table keys
  213.  *     2   generate table values
  214.  *
  215.  *  Carefully generate each element exactly once, even if the hash chains
  216.  *  split while suspended.  Do this by recording the state of things at the
  217.  *  time of the split and checking past history when starting to process a
  218.  *  new chain.
  219.  *
  220.  *  Elements inserted or deleted while the generator is suspended may or
  221.  *  may not be generated. 
  222.  *
  223.  *  We assume that no structure *shrinks* after its initial creation; they
  224.  *  only *grow*.
  225.  */
  226.  
  227. AgtDcl(hgener)
  228.    {
  229.    int i, segnum;
  230.    word d, m, func, slotnum;
  231.    uword hn;
  232.    union block *ep;
  233.  
  234.    word tmask;        /* structure mask before suspension */
  235.    word sgmask[HSegs];    /* mask being used when the segment was created */
  236.    uword sghash[HSegs];    /* hashnum in process when the segment was created */
  237.  
  238.    for (i = 0; i < HSegs; i++)
  239.       sghash[i] = sgmask[i] = 0;        /* set initial state */
  240.    tmask = BlkLoc(Arg1)->table.mask;
  241.  
  242.    func = IntVal(Arg2);                /* save function code */
  243.    Arg2.dword = D_Telem;            /* use Arg2 to tend address */
  244.  
  245.    for (segnum = 0; segnum < HSegs; segnum++) {
  246.       if (BlkLoc(Arg1)->table.hdir[segnum] == NULL)
  247.          break;
  248.       for (slotnum = 0; slotnum < segsize[segnum]; slotnum++) {
  249.          ep = BlkLoc(Arg1)->table.hdir[segnum]->hslots[slotnum];
  250.          /*
  251.           * Check to see if parts of this hash chain were already processed.
  252.           *  This could happen if the elements were in a different chain,
  253.           *  but a split occurred while we were suspended.
  254.           */
  255.          for (i = segnum; (m = sgmask[i]) != 0; i--) {
  256.             d = (word)(m & slotnum) - (word)(m & sghash[i]);
  257.             if (d < 0)            /* if all elements processed earlier */
  258.                ep = NULL;        /* skip this slot */
  259.             else if (d == 0) {
  260.                /*
  261.                 * This chain was split from its parent while the parent was
  262.                 *  being processed.  Skip past elements already processed.
  263.                 */
  264.                while (ep != NULL && ep->telem.hashnum <= sghash[i])
  265.                   ep = ep->telem.clink;
  266.                }
  267.             }
  268.          /*
  269.           * Process the elements of the hash chain, in turn.
  270.           */
  271.          while (ep != NULL) {
  272.             switch ((int)func) {
  273.                case 0:  Arg0 = ep->selem.setmem;  break;
  274.                case 1:  Arg0 = ep->telem.tref;    break;
  275.                case 2:  Arg0 = ep->telem.tval;    break;
  276.                }
  277.             BlkLoc(Arg2) = ep;        /* save pointer, so it gets tended */
  278.             Suspend;            /* suspend, returning current element */
  279.             ep = BlkLoc(Arg2);        /* restore pointer */
  280.  
  281.             if (BlkLoc(Arg1)->table.mask != tmask &&
  282.                   (ep->telem.clink == NULL ||
  283.                   ep->telem.clink->telem.hashnum != ep->telem.hashnum)) {
  284.                /*
  285.                 * The set or table's hash buckets split, once or more, while
  286.                 *  we were suspended.  (We notice this unless the next entry
  287.                 *  has same hash value as the current one.  In that case we
  288.                 *  ignore it for now and will pick it up on the next pass.)
  289.                 *
  290.                 * Make a note of the current state.
  291.                 */
  292.                hn = ep->telem.hashnum;
  293.                for (i = 1; i < HSegs; i++)
  294.                   if ((((word)HSlots) << (i - 1)) > tmask) {
  295.                      /*
  296.                       * For the newly created segments only, save the mask and
  297.                       *  hash number being processed at time of creation.
  298.                       */
  299.                      sgmask[i] = tmask;
  300.                      sghash[i] = hn;
  301.                   }
  302.                tmask = BlkLoc(Arg1)->table.mask;
  303.                /*
  304.                 * Find the next element in our original segment by starting
  305.                 *  from the beginning and skipping through the current hash
  306.                 *  number.  We can't just follow the link from the current
  307.                 *  element, because it may have moved to a new segment.
  308.                 */
  309.                ep = BlkLoc(Arg1)->table.hdir[segnum]->hslots[slotnum];
  310.                while (ep != NULL && ep->telem.hashnum <= hn)
  311.                   ep = ep->telem.clink;
  312.                }
  313.  
  314.             else {
  315.                /*
  316.                 * Nothing happened during the suspend, or else if it did we're
  317.                 *  between items with identical hash numbers.  Just move on.
  318.                 */
  319.                ep = ep->telem.clink;
  320.                }
  321.             }
  322.          }
  323.       }
  324.    Fail;
  325.    }
  326.  
  327. /*
  328.  * hgrow - split a hashed structure (doubling the buckets) for faster access.
  329.  */
  330.  
  331. novalue hgrow(dp)
  332. dptr dp;
  333.    {
  334.    register union block **tp0, **tp1, *ep;
  335.    register word newslots, slotnum, segnum;
  336.    struct b_set *ps;
  337.    struct b_slots *seg, *newseg;
  338.    union block **curslot;
  339.  
  340.    ps = (struct b_set *)BlkLoc(*dp);
  341.    if (ps->hdir[HSegs-1] != NULL)
  342.       return;                /* can't split further */
  343.    newslots = ps->mask + 1;
  344.    if (blkreq(sizeof(struct b_slots) + (newslots - HSlots) * WordSize) == Error)
  345.       return;                /* sorry, no memory */
  346.    ps = (struct b_set *)BlkLoc(*dp);    /* refresh address -- may have moved */
  347.    newseg = alcsegment(newslots);
  348.  
  349.    curslot = newseg->hslots;
  350.    for (segnum = 0; (seg = ps->hdir[segnum]) != NULL; segnum++)
  351.       for (slotnum = 0; slotnum < segsize[segnum]; slotnum++)  {
  352.          tp0 = &seg->hslots[slotnum];    /* ptr to tail of old slot */
  353.          tp1 = curslot++;        /* ptr to tail of new slot */
  354.          for (ep = *tp0; ep != NULL; ep = ep->selem.clink) {
  355.             if ((ep->selem.hashnum & newslots) == 0) {
  356.                *tp0 = ep;        /* element does not move */
  357.                tp0 = &ep->selem.clink;
  358.                }
  359.             else {
  360.                *tp1 = ep;        /* element moves to new slot */
  361.                tp1 = &ep->selem.clink;
  362.                }
  363.             }
  364.          *tp0 = *tp1 = NULL;
  365.          }
  366.    ps->hdir[segnum] = newseg;
  367.    ps->mask = (ps->mask << 1) | 1;
  368.    }
  369.  
  370. /*
  371.  * hshrink - combine buckets in a set or table that is too sparse.
  372.  *
  373.  *  Call this only for newly created structures.  Shrinking an active structure
  374.  *  can wreak havoc on suspended generators.
  375.  */
  376. novalue hshrink(dp)
  377. dptr dp;
  378.    {
  379.    register union block **tp, *ep0, *ep1;
  380.    int topseg, curseg;
  381.    word slotnum;
  382.    struct b_set *ps;
  383.    struct b_slots *seg;
  384.    union block **uppslot;
  385.  
  386.    ps = (struct b_set *)BlkLoc(*dp);
  387.    topseg = 0;
  388.    for (topseg = 1; topseg < HSegs && ps->hdir[topseg] != NULL; topseg++)
  389.       ;
  390.    topseg--;
  391.    while (TooSparse(ps)) {
  392.       uppslot = ps->hdir[topseg]->hslots;
  393.       ps->hdir[topseg--] = NULL;
  394.       for (curseg = 0; (seg = ps->hdir[curseg]) != NULL; curseg++)
  395.          for (slotnum = 0; slotnum < segsize[curseg]; slotnum++)  {
  396.             tp = &seg->hslots[slotnum];        /* tail pointer */
  397.             ep0 = seg->hslots[slotnum];        /* lower slot entry pointer */
  398.             ep1 = *uppslot++;            /* upper slot entry pointer */
  399.             while (ep0 != NULL && ep1 != NULL)
  400.                if (ep0->selem.hashnum < ep1->selem.hashnum) {
  401.                   *tp = ep0;
  402.                   tp = &ep0->selem.clink;
  403.                   ep0 = ep0->selem.clink;
  404.                   }
  405.                else {
  406.                   *tp = ep1;
  407.                   tp = &ep1->selem.clink;
  408.                   ep1 = ep1->selem.clink;
  409.                   }
  410.             while (ep0 != NULL) {
  411.                *tp = ep0;
  412.                tp = &ep0->selem.clink;
  413.                ep0 = ep0->selem.clink;
  414.                }
  415.             while (ep1 != NULL) {
  416.                *tp = ep1;
  417.                tp = &ep1->selem.clink;
  418.                ep1 = ep1->selem.clink;
  419.                }
  420.             }
  421.       ps->mask >>= 1;
  422.       }
  423.    }
  424.  
  425. /*
  426.  * memb - sets res flag to 1 if x is a member of a set or table, or to 0 if not.
  427.  *  Returns a pointer to the word which points to the element, or which
  428.  *  would point to it if it were there.
  429.  */
  430.  
  431. union block **memb(pb, x, hn, res)
  432. union block *pb;
  433. dptr x;
  434. register uword hn;
  435. int *res;                /* pointer to integer result flag */
  436.    {
  437.    struct b_set *ps;
  438.    register union block **lp;
  439.    register struct b_selem *pe;
  440.    register uword eh;
  441.  
  442.    ps = (struct b_set *)pb;
  443.    lp = hchain(pb, hn);
  444.    /*
  445.     * Look for x in the hash chain.
  446.     */
  447.    *res = 0;
  448.    while ((pe = (struct b_selem *)*lp) != NULL) {
  449.       eh = pe->hashnum;
  450.       if (eh > hn)            /* too far - it isn't there */
  451.          return lp;
  452.       else if ((eh == hn) && (equiv(&pe->setmem, x)))  {
  453.          *res = 1;
  454.          return lp;
  455.          }
  456.       /*
  457.        * We haven't reached the right hashnumber yet or
  458.        *  the element isn't the right one so keep looking.
  459.        */
  460.       lp = &(pe->clink);
  461.       }
  462.    /*
  463.     *  At end of chain - not there.
  464.     */
  465.    return lp;
  466.    }
  467.